BOJ 1149

1149 RGB거리

tip

Clicking the heading will take you to the BOJ problem.

Solution

DP 테이블을 정의할 때 어려웠다. i번째 집을 j색으로 칠한 경우의 누적 최소 비용이었는데 누적한 비용을 넣는 건 생각을 못 했다.

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n)]
dp[0] = cost[0][:]

for i in range(1, n):
    dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])

print(min(dp[n-1]))